A recent development in computer networking is the notion of Software-Defined Networks (“SDN”s), whereby a network is allowed to customize its behaviors through centralized policies at a conceptually centralized network controller. In particular, OpenFlow (introduced in N. McKeown, and T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, J. Turner, “OpenFlow: Enabling Innovation in Campus Networks”, SIGCOMM Comput. Commun. Rev., April 2008, 38, pp. 69-74, which is incorporated herein by reference in its entirety) has established (1) flow tables as a standard data-plane abstraction for distributed switches, (2) a protocol for the centralized controller to install forwarding rules and query state at switches, and (3) a protocol for the switches to forward to the controller packets not matching any rules in its switch-local forwarding table. We refer to the programming of the centralized controller as “SDN programming”, and a network operator who conducts SDN programming as an “SDN programmer”, or just “programmer”.
Data communication networks, referred to herein as “networks”, can include interconnected switches, virtual switches, hubs, routers, and/or other devices configured to handle data packets as they pass through the network. These devices are referred to herein as “network elements”. We also use the term “switch” synonymously with “network element”, unless otherwise noted.
Sources and destinations may be considered endpoints on the network. Endpoint systems, along with the users and services that reside on them, are referred to herein as “endpoints”. We also use the term “host” synonymously with endpoint. As used herein, the term “data forwarding element” refers to an element in the network that is not an endpoint, and that is configured to receive data from one or more endpoints and/or other network elements and to forward data to one or more other endpoints and/or other network elements.
Network elements, including data forwarding elements, may have “ports” at which they interconnect with other devices via some physical medium, such as Ethernet cable or optical fibre. We refer to a switch port which connects the port to an endpoint as an “edge port” and the communication link connecting the endpoint to the switch port as an “edge link”. We refer to a switch port which connects the port to another switch port (typically on a different switch) as a “core port” and the link connecting the two switches as a “core link”.
The terms “topology” and “network topology” refer to the manner in which switches are interconnected. A network topology is often mathematically represented as a finite graph, including a set of nodes representing network elements, a set of links representing communication links, and a function indicating, for each link, the two network elements connected by the link as well as the ports at which the link attaches on the two network elements. This information can be augmented with extra attributes of nodes and links, such as the bandwidth of each link.
A “packet” or “frame” is the fundamental unit of data to be communicated in a packet-switched computer network. A packet contains a sequence of bits, wherein some portion of those bits, typically the initial bits, form a “header” (also referred to as a “frame header” or “packet header”) which contains information used by the network to provide network services. For example, an Ethernet frame header includes the sender (also known as the source) and the recipient (also known as the destination) Ethernet addresses. The header is structured into “fields” which are located in specific positions in the header. For example, the Ethernet frame header includes fields for the source and destination Ethernet addresses of the frame. We define the symbolic notation p.a to denote the value of field a in the packet p.
The term “forwarding behavior” denotes the manner in which packets are treated in a network, including the manner in which packets are switched through a sequence of switches and links in the network. The forwarding behavior may also refer to additional processing steps applied to packets during forwarding, such as transformations applied to a data packet (e.g. tagging packets with virtual local area network (VLAN) identifiers) or treating the packet with a service class in order to provide a quality of service (QoS) guarantee. We use the term “global forwarding behavior of a packet” to refer to the manner in which a packet is forwarded from the edge port at which it enters the network to other edge ports at which it exits. We use the phrase “global packet forwarding behavior” to refer to a characterization of the global forwarding behavior of all packets.
Network elements may implement a protocol similar to OpenFlow (www.opennetworking.org/about/onf-documents; see, e.g., “OpenFlow Switch Specification, Version 1.0.0, Dec. 31, 2009, which is incorporated herein by reference in its entirety), wherein a network element has a local collection of prioritized rules with which to process packets, known herein as a “rule set”. We designate such network elements as “Openflow-like network elements”. Each rule may have a priority level, a condition that specifies which packets it may apply to, and an action with which to process applicable packets. Openflow-like network elements communicate with a component known as the “controller,” which may be implemented as one or more computers such as control servers. The controller interacts with an Openflow-like network element in order to control its packet processing behavior, typically by configuring the rule sets of the Openflow-like network elements.